home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 15066 < prev    next >
Encoding:
Text File  |  1996-08-05  |  9.0 KB  |  242 lines
  1. Path: mayne.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c,comp.unix.programmer
  4. Subject: Re: Q: '\n' character
  5. Date: 16 Apr 1996 13:32:33 -0700
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4l1051INN7r7@mayne.ugrad.cs.ubc.ca>
  8. References: <4kj66f$k0o@ren.cei.net> <AD97189A966891F2@mcdiala02.it.luc.edu> <4ktn04INNoev@keats.ugrad.cs.ubc.ca> <4ku8f9$d3o@mark.ucdavis.edu>
  9. NNTP-Posting-Host: mayne.ugrad.cs.ubc.ca
  10.  
  11. In article <4ku8f9$d3o@mark.ucdavis.edu>,
  12. James Knight <knight@quad.cs.ucdavis.edu> wrote:
  13. >I just bypass all of the problems with fgets using the function below.  It handles
  14.  
  15. OK, here is mine!
  16.  
  17. I was 30 minutes late for a 8:30 number theory final because of this, so I may
  18. not graduate.
  19.  
  20. My ``general'' line reading was tested on various binary and text files,
  21. including an eight megabyte file full of zeroes, created on the linux system
  22. with the command ``dd if=/dev/zero of=testfile bs=1024 count=8192''.
  23.  
  24. The function is configurable with respect to:
  25.  
  26. - handling of null characters (they are kept by default, or are optionally
  27.   converted to CHAR_MAX characters, or are optionally taken to be alternate
  28.   line terminators equivalent to '\n'.
  29.  
  30. - handling of memory allocation faults. In the event that a memory allocation
  31.   fails, the routine has the option of either free()ing what it has so far
  32.   and returning a null pointer, or keeping what it has so far (after adding
  33.   proper zero termination as in a successful case).
  34.  
  35. The function reports, in the form of binary flags, whether:
  36.  
  37. - EOF was encountered. (if this happens when reading something other than
  38.   the first character of the line, the line is also treated as incomplete).
  39. - Whether the line was incomplete (this is also reported whenever a null
  40.   character is interpreted as the end of a line). So if EOF is _not_ reported,
  41.   but premature end of line _is_ reported, it means that the line ended with
  42.   a null character rather than a newline (of course, this interpretation of
  43.   null characters must be enabled for this to occur).
  44. - whether the function ran out of memory, or overflowed the maximum allocation
  45.   size, when reading the line. NULL is returned either if the keep flag
  46.   has not been specified, and always when the very first malloc() fails (since
  47.   then there is no meaningful buffer pointer to revert to).
  48.  
  49. The empirical performance on a Linux P90/32MB system was: 2.5 seconds of user
  50. time and 2.5 seconds of system time in reading a single line of 8MB zero
  51. characters, at about 50% CPU; in reading the same file, but interpreting each
  52. zero as a newline character, it required 81seconds of user time, two seconds of
  53. system time, at 93% CPU.
  54.  
  55. I have checked it against its handling of malloc() failure by artificially
  56. restricting the data segment size of the process to 1024K (via the ulimit
  57. built-in command of the GNU Bourne-Again Shell), and had it try to read an
  58. eight megabyte long line. It correctly returned NULL when partial keeping was
  59. not specified, and returned about 800-900K when partial keeping in the event of
  60. allocation failure _was_ specified.
  61.  
  62. I have also tested all kinds of cases, and all the options in combination with
  63. malloc failure. One test I did with the sample harness program was to filter
  64. the operating system kernel through it. A file comparison program indicated only
  65. the difference that an extra newline was added in the destination (which could
  66. have been taken care of in the test program by checking for an incomplete
  67. line).
  68.  
  69. The only feature that is untested is the overflow check for computing a larger
  70. buffer size, since this may exceed size_t for a sufficiently large file size.
  71. (ANSI guarantees a maximum size_t of only 32767).
  72.  
  73. BUGS: 
  74.  
  75. - when the program is unable to resize the buffer to the actual bytes that
  76. were read, it gives up and returns the oversized buffer (but gives the correct
  77. line length nevertheless). This shouldn't happen in pratice, with a sound
  78. realloc() implementation.
  79.  
  80. - input/output flags could be combined into a single parameter, as with
  81. the select() system call, for example.
  82.  
  83. --------
  84.  
  85. The freadln.h header file:
  86.  
  87. typedef enum fr_inflg {
  88.         FR_NOI =        0x00,           /* no input flags               */
  89.         FR_CONV =       0x01,           /* convert null chars to 127    */
  90.         FR_NL =         0x02,           /* treat nulls as newlines      */
  91.         FR_KEEP =       0x04            /* if NOMEM, keep partial line  */
  92. } fr_inflg;
  93.  
  94. typedef enum fr_outflg {
  95.         FR_NOO =        0x00,           /* no output flags              */
  96.         FR_EOF =        0x01,           /* EOF was encountered          */
  97.         FR_NONL =       0x02,           /* line did not end in newline  */
  98.         FR_NOMEM =      0x04,           /* out of memory                */
  99.         FR_OFLOW =      0x08            /* allocation size_t overflow   */
  100. } fr_outflg;
  101.  
  102. char *freadln(const fr_inflg inf, fr_outflg *ouf, size_t *len, FILE *stream);
  103.  
  104.  
  105. --------
  106.  
  107. The freadln.c implementation:
  108.  
  109. #include <stdio.h>
  110. #include <stdlib.h>
  111. #include <limits.h>
  112.  
  113. #include "freadln.h"
  114.  
  115. #define INIT_SIZE1      55              /* Fibonacci numbers            */
  116. #define INIT_SIZE2      89
  117.  
  118. char *freadln(const fr_inflg inf, fr_outflg *ouf, size_t *len, FILE *stream)
  119.  
  120. {
  121.         size_t oldsize = INIT_SIZE1, cursize = INIT_SIZE2, newsize;
  122.         char *line, *pline, *limit, *new;
  123.  
  124.         *ouf = FR_NOO;
  125.  
  126.         pline = line = malloc(cursize);
  127.  
  128.         if (!line) {
  129.                 *ouf = FR_NOMEM;
  130.                 goto failure;
  131.         }
  132.  
  133.         limit = line + cursize - 2;     /* guarantee room for null      */
  134.  
  135.         while (1) {
  136.                 int c = getc(stream);
  137.  
  138.                 switch(c) {
  139.                 case '\0':
  140.                         if (inf & FR_NL)        /* nulls terminate      */
  141.                                 goto badend;
  142.                         if (inf & FR_CONV) {    /* nulls get replaced   */
  143.                                 c = CHAR_MAX;
  144.                                 goto addchar;
  145.                         }
  146.                         goto addchar;
  147.                         break;
  148.                 case EOF:
  149.                         *ouf = FR_EOF;
  150.                         if (pline == line)      /* first character?     */
  151.                                 goto success;
  152.                 badend:                         /* line end w/o newline */
  153.                         *ouf |= FR_NONL;
  154.                 case '\n':
  155.                         goto success;           /* jump out of loop     */
  156.                 addchar:
  157.                 default:
  158.                         *pline++ = c;
  159.                         break;
  160.                 }
  161.  
  162.                 if (pline >= limit) {           /* if buffer is full... */
  163.                         newsize = cursize + oldsize;
  164.                         if (newsize < cursize) {        /* overflow!    */
  165.                                 *ouf = FR_OFLOW;
  166.                                 if (inf & FR_KEEP)
  167.                                         goto success;
  168.                                 free(line);
  169.                                 goto failure;
  170.                         }
  171.                         new = realloc(line, newsize);
  172.                         if (!new) {
  173.                                 *ouf = FR_NOMEM;
  174.                                 if (inf & FR_KEEP)
  175.                                         goto success;
  176.                                 free(line);
  177.                                 goto failure;
  178.                         }
  179.                         oldsize = cursize;
  180.                         cursize = newsize;
  181.                         pline = new + (pline - line);
  182.                         line = new;
  183.                         limit = line + cursize - 2;
  184.                 }
  185.         }
  186.  
  187. success:
  188.         *pline++ = '\0';                /* null-terminate               */
  189.         *len = pline - line - 1;        /* calculate line length        */
  190.         new = realloc(line, *len + 1);  /* try to trim buffer down      */
  191.         return (new) ? new : line;      /* if cannot, ah well...        */
  192.  
  193. failure:
  194.         return NULL;
  195. }
  196.  
  197.  
  198.  
  199. --------
  200.  
  201. Sample main ``test harness'' filter:
  202.  
  203. #include <stdio.h>
  204. #include <stdlib.h>
  205. #include "freadln.h"
  206.  
  207. int main(int argc, char **argv)
  208.  
  209. {
  210.         fr_inflg inf, ouf;
  211.         size_t len, maxlen = 0;
  212.         char *line;
  213.  
  214.         if ((++argv, --argc) && *argv)
  215.                 inf = atoi(*argv);
  216.         else    
  217.                 inf = FR_NOI;
  218.  
  219.         while ((line = freadln(inf, &ouf, &len, stdin))) {
  220.                 fwrite(line, 1, len, stdout);
  221.                 free(line);
  222.                 if (len > maxlen)
  223.                         maxlen = len;
  224.                 putchar('\n');
  225.                 if (ouf & (FR_NOMEM|FR_OFLOW)) {
  226.                         fprintf(stderr,"ouf == %d, maxlen == %d\n",ouf,maxlen);
  227.                         exit(EXIT_FAILURE);
  228.                 }
  229.                 if (ouf & FR_EOF) {
  230.                         fprintf(stderr,"maxlen == %d\n",maxlen);
  231.                         exit(EXIT_SUCCESS);
  232.                 }
  233.         }
  234.  
  235.         fprintf(stderr,"line === NULL, maxlen = %d\n",maxlen);
  236.         return EXIT_FAILURE;
  237. }
  238. ~
  239.  
  240. -- 
  241. I'm not really a jerk, but I play one on Usenet.
  242.